﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

int x1, y1, x2, y2;
int n, m;
vector<string> vec;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
vector<vector<int>> exist;
void dfs(int nowX, int nowY, int step, int& result)//这里采用dfs会超时，dfs不太适合用来求最短路径，比较适合用来求路径的条数
{
    exist[nowX][nowY] = 1;
    if (nowX == x2 && nowY == y2)
    {
        result = min(step, result);
        return;
    }

    if (vec[nowX][nowY] == '*')
    {
        return;
    }

    for (int k = 0; k < 4; ++k)
    {
        int newx = nowX + dx[k];
        int newy = nowY + dy[k];
        if (newx >= 0 && newx < n && newy >= 0 && newy < m && !exist[newx][newy])
        {
            dfs(newx, newy, step + 1, result);
        }
    }
    exist[nowX][nowY] = 0;
}

int main()
{
    cin >> n >> m;

    cin >> x1 >> y1 >> x2 >> y2;
    x1 -= 1;
    x2 -= 1;
    y1 -= 1;
    y2 -= 1;

    exist.assign(n, vector<int>(m, 0));
    vec.assign(n, "");

    for (int i = 0; i < n; ++i)
    {
        cin >> vec[i];
    }

    if (vec[x2][y2] == '*')
    {
        cout << -1 << endl;
        return 0;
    }

    int result = INT_MAX;
    dfs(x1, y1, 0, result);

    if (result == INT_MAX)
    {
        cout << -1 << endl;
        return 0;
    }

    cout << result << endl;
    return 0;
}

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
using namespace std;

int x1, y1, x2, y2;
int n, m;
vector<string> vec;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
vector<vector<int>> exist;
int bfs()
{
    queue<pair<int, int>> q;
    q.emplace(x1, y1);

    exist[x1][y1] = 0;//起点的步数为0

    while (!q.empty())
    {
        auto [nowX, nowY] = q.front();
        q.pop();

        for (int k = 0; k < 4; ++k)
        {
            int newx = nowX + dx[k];
            int newy = nowY + dy[k];
            if (newx >= 0 && newx < n && newy >= 0 && newy < m && exist[newx][newy] == -1 && vec[newx][newy] != '*')
            {
                exist[newx][newy] = exist[nowX][nowY] + 1;
                q.emplace(newx, newy);

                if (newx == x2 && newy == y2)//到达终点
                {
                    return exist[newx][newy];
                }
            }
        }
    }

    return -1;
}

int main()
{
    cin >> n >> m;

    cin >> x1 >> y1 >> x2 >> y2;
    x1 -= 1;
    x2 -= 1;
    y1 -= 1;
    y2 -= 1;

    exist.assign(n, vector<int>(m, -1));//-1表示还没有被访问过，其他数字表示从x1,y1到达这里的步数
    vec.assign(n, "");

    for (int i = 0; i < n; ++i)
    {
        cin >> vec[i];
    }

    if (vec[x2][y2] == '*')
    {
        cout << -1 << endl;
        return 0;
    }

    cout << bfs() << endl;
    return 0;
}

/*
给定一个n×m的网格，在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。
网格中的一些格子上放置有障碍物，放有障碍物的格子不能到达。求从(𝑥𝑠,𝑦𝑠)(xs,ys)到(xt,yt)最少的移动次数。若不能到达，输出−1。
输入描述：
第一行输入两个整数n,m (1≤n,m≤1000)，表示网格大小。
第二行输入四个整数xs,ys,xt,yt(1≤xs,xt≤n,1≤ys,yt≤m)，表示起点和终点的坐标。
接下来的n行，每行输入一个长度为m的字符串。
其中，第i行第j个字符表示第i行第j列的格子上的障碍物情况，若字符为'*'，则格子上有障碍物
，若字符为'.'，则格子上没有障碍物。
保证起点不存在障碍物。
输出描述：
输出一行一个整数，表示从(𝑥𝑠,𝑦𝑠)(xs ,ys)到(𝑥𝑡,𝑦𝑡)(xt,yt)最少的移动次数。

示例1
输入：
5 5
1 1 5 5
.....
****.
.....
**.**
.....
输出：
12
*/

